package com.xiaobai;

import cn.hutool.core.util.ArrayUtil;
import cn.hutool.core.util.RandomUtil;

import java.util.Arrays;

public class SortTest {

    public static void main(String[] args) {
        int[] numsTT = RandomUtil.randomInts(10000);
        int[] nums = ArrayUtil.clone(numsTT);
        long start = System.currentTimeMillis();
        bubbleSort(nums);
        System.out.println("冒泡排序：" + (System.currentTimeMillis() - start));
        nums = ArrayUtil.clone(numsTT);
        start = System.currentTimeMillis();
        selectionSort(nums);
        System.out.println("选择排序：" + (System.currentTimeMillis() - start));
        nums = ArrayUtil.clone(numsTT);
        start = System.currentTimeMillis();
        insertSort(nums);
        System.out.println("插入排序：" + (System.currentTimeMillis() - start));
        nums = ArrayUtil.clone(numsTT);
        start = System.currentTimeMillis();
        Arrays.sort(nums);
        System.out.println("api排序：" + (System.currentTimeMillis() - start));
    }

    /**
     * 插入排序
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int len = arr.length;

        for (int i = 1; i < len; ++i) {
            for (int j = i; j > 0 && arr[j - 1] >= arr[j]; --j) {
                swap(arr, j, j - 1);
            }
        }

    }

    /**
     * 选择排序
     *
     * @param arr
     */
    public static void selectionSort(int[] arr) {
        int len = arr.length;

        for (int i = 0; i < len - 1; ++i) {
            int min = i;

            for (int j = i + 1; j < len; ++j) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }

            swap(arr, i, min);
        }

    }

    /**
     * 冒泡排序
     *
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        int len = arr.length;

        for (int i = 0; i < len - 1; ++i) {
            for (int j = 0; j < len - i - 1; ++j) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
